package _interview100;

import _object.ListNode;

/**
 * 25. K 个一组翻转链表
 */
public class No25 {
    /**
     * 1.递归
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        // 边界条件判断
        if (k == 1 || head == null) return head;
        // 判断当前长度是否小于k
        ListNode p0 = head;
        for (int i = 0; i < k - 1; i++) {
            p0 = p0.next;
            if (p0 == null) return head;
        }
        // 翻转k个链表
        ListNode pre = null, cur = head, nex;
        for (int i = 0; i < k; i++) {
            nex = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nex;
        }
        // 继续检索下一组
        head.next = reverseKGroup(cur, k);
        return pre;
    }

    /**
     * 2.迭代
     */
    public ListNode reverseKGroup2(ListNode head, int k) {
        ListNode nex, dummy = new ListNode(-1), p0 = head, p1;
        dummy.next = head;

        int n = 1;
        while (p0.next != null) {
            p0 = p0.next;
            n++;
        }
        p0 = dummy;

        for (int j = 0; j < n / k; j++) {
            ListNode pre = null, cur = p0.next;
            for (int i = 0; i < k; i++) {
                nex = cur.next;
                cur.next = pre;
                pre = cur;
                cur = nex;
            }
            p1 = p0.next;
            p0.next.next = cur;
            p0.next = pre;
            p0 = p1;
        }
        return dummy.next;
    }

}
